Jimmy :
Let the pseudocode:\nfor i = 1 to length(A)\n x = A[i]\n j = i - 1\n while j >= 0 and A[j] > x\n A[j+1] = A[j]\n j = j - 1\n end while\n A[j+1] = x\n end for \n\nComplexity of Insertion Sort\nInsertion sort runs in O(n) time in its best case and runs in O(n^2) in its worst and average cases.\nBest Case Analysis:\nInsertion sort performs two operations: it scans through the list, comparing each pair of elements, and it swaps elements if they are out of order. Each operation contributes to the running time of the algorithm.\nIf the input array is already in sorted order, insertion sort compares O(n) elements and performs no swaps (in the pseudocode above, the inner loop is never triggered). Therefore, in the best case, insertion sort runs in O(n) time.\nWorst and Average Case Analysis:\nThe worst case for insertion sort will occur when the input list is in decreasing order. To insert the last element, we need at most n-1 comparisons and at most n-1 swaps. To insert the second to last element, we need at most n-2 comparisons and at most n-2 swaps, and so on.. The number of operations needed to perform insertion sort is therefore: 2 × (1+2+⋯+n−2+n−1).\nTo calculate the recurrence relation for this algorithm, use the following:\n2(n−1)(n−1+1)/2 =n(n−1)\nUse the master theorem to solve this recurrence for the running time. As expected, the algorithm's complexity is O(n^2)\nWhen analysing algorithms- the average case often has the same complexity as the worst case. So insertion sort, on average, takes O(n^2) time.\nInsertion sort has a fast best-case running time and is a good sorting algorithm to use if the input list is already mostly sorted. For larger or more unordered lists, an algorithm with a faster worst and average-case running time, such as merge sort, would be a better choice.\nInsertion sort is a stable sort with a space complexity of O(1).",
2021-12-25T06:13:39
Cody Piersall :
In short, the worst case is when your list is in the exact opposite order you need. In that case:\n\n\nFor the first item, you make 0 comparisons, of course. \nFor the second item, you compare it to the first item and find that they are not in the right position; you've made 1 comparison. \nFor the third, you compare it with both, and find that the third has to go to the top. You've made 2 comparisons.\nThis goes on; for every following value, you make one more comparison.\nFinally, for the nth item, you make n - 1 comparisons. \n\n\nIf you add up the number of comparisons you make for the worst case, you'll see that it is 0 + 1 + 2 + ... + n-1, which is equal to (n^2 - n) / 2 comparisons for the worst case, which is O(n^2). (The part that determines the complexity is when we consider large n, in which case the n^2 term dominates)",
2014-01-19T01:02:29